﻿// 525. 连续数组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/contiguous-array/description/

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。



示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。


提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1
*/


class Solution {
public:
    int presum[100010];
    int findMaxLength(vector<int>& nums) {
        memset(presum,0,sizeof presum);
        nums.insert(nums.begin(), -99);

        for (int i = 1; i < nums.size(); i++) {
            int val = 1;
            if (nums[i] == 0) { val = -1; }
            presum[i] = presum[i - 1] + val;
        }
        int ans = 0;
        unordered_map<int, int> mm;
        for (int i = 1; i < nums.size(); i++) {
            if (presum[i] == 0) {
                ans = max(ans, i);
            }
            int find = presum[i];
            if (mm.count(find) != 0) {
                ans = max(ans, i - mm[find]);
            }
            if (mm.count(presum[i]) == 0) mm[presum[i]] = 99999999;
            mm[presum[i]] = min(mm[presum[i]], i);
        }


        return ans;
    }
};


int main()
{
    Solution s;
    vector<int>  v{ 0,0,1};
    s.findMaxLength(v);

	return 0;
}

 